# !/usr/bin/env python
# -*- coding=utf-8 -*-

import time


def pack1(w, v, C): #每个东西只能选择一次
    dp = [[0 for _ in range(C+1)] for _ in range(len(w)+1)]
    for i in range(1, len(w)+1):
        for j in range(1, C+1):
            if j < w[i-1]: #如果剩余容量不够新来的物体 直接等于之前的
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+ v[i-1])
    for each in dp:
        print(each)
    return dp[len(w)][C]


def pack2(w, v, c):
    # 它是先得到第一行的值，存到dp中，然后再直接用dp相当于就是上一行的值，所以下面必须用逆序
    # 否则dp[j-w[i-1]]可能会用到你本行的值，从大到小就不会
    dp = [0 for _ in range(c+1)]
    for i in range(1, len(w)+1):
        for j in reversed(range(1, c+1)):  #这里必须用逆序
            if w[i-1] <= j:
                dp[j] = max(dp[j], dp[j-w[i-1]]+v[i-1])
    print(dp)
    return dp[c]


def pack3(w, v, C):   #每个东西能选择多次 完全背包问题
    dp = [[0 for _ in range(C+1)] for _ in range(len(w)+1)]
    for i in range(1, len(w)+1):
        for j in range(1, C+1):
            if j < w[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-w[i-1]] + v[i-1])
    # for i in dp:
    #     print(i)
    return dp[-1][-1]


def pack4(w, v, C):
    dp = [0 for _ in range(C+1)]
    for i in range(1, len(w)+1):
        for j in (range(1, C+1)):
            if w[i-1] <= j:
                dp[j] = max(dp[j], dp[j-w[i-1]]+v[i-1])
    # print(dp)
    return dp[-1]


def main():
    # print(pack1([2, 3, 4, 5], [3, 4, 5, 6], 8))
    # print(pack2([2, 3, 4, 5], [3, 4, 5, 6], 8))
    weights = list(range(2, 10000))
    values = list(range(3, 10001))
    # weights = [2, 3, 4, 5]
    # values = [3, 4, 5, 6]
    capacity = 10000
    print(pack4(weights, values, capacity))
    # print(pack4(weights, values, 8000))


if __name__ == '__main__':
    start_time = time.time()
    main()
    print("total_time:", time.time() - start_time)

